package LeetCode.exercise;

import java111.ListNode;

public class LC143 {
    public static void main(String[] args) {
        LC143 l = new LC143();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        l.reorderList(node1);
        System.out.println();
    }

    public void reorderList(ListNode head) {
        ListNode middle = findMiddleNode(head);
        ListNode head2 = reverseNode(middle);
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        ListNode cur1 = head;
        ListNode cur2 = head2;
        while(cur1 != middle){
            ListNode cur1Next = cur1.next;
            ListNode cur2Next = cur2.next;
            cur.next = cur1;
            cur = cur.next;
            cur.next = cur2;
            cur = cur.next;
            cur1 = cur1Next;
            cur2 = cur2Next;
        }
        head = newHead.next;
    }
    // 寻找链表中间节点
    public ListNode findMiddleNode(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
            if(fast.next != null){
                fast = fast.next;
            }
        }
        return slow;
    }
    // 逆置链表
    public ListNode reverseNode(ListNode head){
        ListNode newHead = new ListNode(0);
        ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = curNext;
        }
        return newHead.next;
    }
}
